#ifndef DATABASE_H
#define DATABASE_H

#include "globals.h"
#include <QMutex>
#include <QList>

namespace db {

enum Flags{
    k_muted_directly =      0x00000001,
    k_muted_by_parent =     0x00000010,
    k_deleted_directly =    0x00000100,
    k_deleted_by_parent =   0x00001000,
};


template <class Data, class Index, class Type>
struct Record
{
    //   template <class D, class I, class T> friend class Database;

    //public:
    typedef Record<Data, Index, Type> Rec;
    typedef Rec* RecId;
    typedef QList< RecId > RecList;


    Record(Data* data_n, const Type& type_n, const Index& index_n, const RecId& parent_n ):
        data(data_n),
        type(type_n),
        index(index_n),
        parent(parent_n),
        prev(NULL),
        next(NULL),
        flags(0),
        children(new RecList)
    {}
    ~Record(){
        delete data;
        foreach (RecId r, *children){r->parent = NULL;}
        if (parent != NULL) parent->children->removeAll(this);
        qDeleteAll(*children);
        delete children;
    }
    bool isDeleted(){return (k_deleted_directly || k_deleted_by_parent) & flags;}
    //protected:
    Data* data;
    Type type;
    Index index;
    Record* parent;
    Record* prev;
    Record* next;
    char flags;
    RecList* children;



};

template <class Data, class Index, class Type>
class Database
{
public:
    typedef Record<Data, Index, Type> Rec;
    typedef Rec * RecId;

    Database( Data* root_data,  const Type& root_type, const Index& root_index){
        root_ = new Rec(root_data, root_type, root_index, NULL);
    }

    ~Database()   {
        delete root_;
    }

    RecId addRecord(Data* data, const Type& type,
                    const Index & sortIndex, RecId parent);
    RecId addRecord(Data* data, const Type& type,
                    const Index & sortIndex); // append to root
    RecId getRootId(){return root_;}

    void deleteRecord(RecId r);
    void moveRecord(RecId record, const Index& new_index);
    QMutex & mutex() {return mutex_;}
    QList <Data*> dumpData();


private:
    RecId record(RecId id){return id;}
    void deleteRecordByParent(RecId r);
    RecId findLeftFromHint(const Index & i, RecId hint);
    Rec* root_;
    QMutex mutex_;
};


template <class Data, class Index, class Type>
Record<Data, Index, Type> * Database<Data, Index, Type>::
addRecord(Data* data, const Type& type, const Index & sortIndex, RecId parent)
{

    Rec* r = new Rec(data, type, sortIndex, parent);
    mutex_.lock();
    Rec* l = findLeftFromHint(sortIndex, parent);
    r->next = l->next;
    if (l->next != NULL) l->next->prev = r;
    r->prev = l;
    l->next = r;
    record(parent)->children->append(r);
    mutex_.unlock();
    return r;
}


template <class Data, class Index, class Type>
Record<Data, Index, Type> *
Database<Data, Index, Type>::addRecord(Data* data, const Type& type,
                                       const Index & sortIndex)
{
    addRecord(data, type, sortIndex, root_);
}

template <class Data, class Index, class Type>
void Database<Data, Index, Type>::deleteRecord(RecId r)
{
    if (r->isDeleted()) return;
    r->flags = r->flags || k_deleted_directly;
    foreach(RecId c, *r->children) deleteRecordByParent(c);
}

template <class Data, class Index, class Type>
void Database<Data, Index, Type>::deleteRecordByParent(RecId r)
{
    if (r->isDeleted()) return;
    r->flags = r->flags || k_deleted_by_parent;
    foreach(RecId c, *r->children) deleteRecordByParent(c);
}

template <class Data, class Index, class Type>
void Database<Data, Index, Type>::moveRecord(RecId r, const Index& new_index)
{

    if (r == root_) return;
    Index offset = new_index - r->index;

    mutex_.lock();
    RecId l = findLeftFromHint(new_index, r->parent);
    r->prev->next = r->next;
    if (r->next != NULL) r->next->prev = r->prev;
    r->next = l->next;
    if (l->next != NULL) r->next->prev = r;
    r->prev = l;
    l->next = r;
    r->index = new_index;
    mutex_.unlock();

    foreach (RecId c, *(r->children)) moveRecord(c, c->index + offset);
}

template <class Data, class Index, class Type>
typename Database<Data, Index, Type>::RecId
Database<Data, Index, Type>::findLeftFromHint(const Index & index, RecId hint){
    Rec* c = record(hint);
    while (true){
        if (index >= c->index){
            if (c->next == NULL) break; // end of list
            if (index < c->next->index) break;
            c = c->next;
        } else { // if index < c->index
            if (c == root_ || c->prev == NULL) break; // head of list
            c = c->prev;
        }
    }
    return c;
}

template <class Data, class Index, class Type>
QList <Data*> Database<Data, Index, Type>::dumpData()
{
    QList <Data*> l;
    for (Rec* c = root_; c = c->next; c!=NULL){
        if (c->flags && (db::k_deleted_directly ||
                         db::k_deleted_by_parent)) continue;
        Data* d = c->data;
        l.append(d);
    }
    return l;
}
};

#endif // DATABASE_H
